package exampleQuestions;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;

class LRU<K, V> {

	private LinkedHashMap<K, V> map;
	private final int size;
	
	private static final float loadFactor = 0.75f;

	public LRU(int size) {
		
		this.size = size;
		int initialCapacity = (int)Math.ceil(size/loadFactor);
		map = new LinkedHashMap<K, V>(initialCapacity, loadFactor, true){
			
			private static final long serialVersionUID = 1;
			
			@Override protected boolean removeEldestEntry (Map.Entry<K,V> eldest) {
				return LRU.this.size < this.size();
			}
		};
	}

	public synchronized void put(K key, V value) {

		map.put(key, value);
	}

	public synchronized V get(K key) {
		return map.get(key);
	}

	public synchronized int usedEntries() {
		return map.size();
	}

	public synchronized Collection<Map.Entry<K, V>> getCollection() {
		return new ArrayList<Map.Entry<K, V>>(map.entrySet());
	}
}

class LRU2<K, V> {

	class Node {
		public Node(K key, V val) {
			this.value = val;
			this.key = key;
		}
		V value;
		K key;
		Node prev, next;
	}

	private HashMap<K, Node> map = new HashMap<K, Node>();
	private int size;
	private Node first, last;

	public LRU2(int size) {
		this.size = size;
	}

	public synchronized void put(K key, V value) {
		
		Node node = null;
		if(!map.containsKey(key)) {
			if(size == map.size()) {
				map.remove(last.key);
				removeLast();
			}
			node = new Node(key, value);
			map.put(key, node);
			addFirst(node);
		} else {
			node = map.get(key);
			remove(node);
			Node newNode = new Node(key, value);
			addFirst(newNode);
			map.put(key, newNode);
			
		}
	}

	public synchronized V get(K key) {
		
		Node n = map.get(key);
		if (n != null) {
			
			remove(n);
			addFirst(n);
			
			return n.value;
		}
		else {
			return null;
		}
	}

	public synchronized int usedEntries() {
		return map.size();
	}

	private void removeLast() {
		remove(last);
	}

	private void addFirst(Node n) {

		if (first == null) {
			first = n;
			last = n;
		} else {
			n.next = first;
			first.prev = n;
			first = n;
		}
	}

	private void remove(Node n) {
		if (n == null) {
			return;
		} else {
			Node tmp = n.next;
			if (tmp != null) {
				tmp.prev = n.prev;
			} else {
				n.next = null;
			}
			
			tmp = n.prev;
			if (tmp != null) {
				tmp.next = n.next;
			}
			
			if (first == n) {
				first = n.next;
			}
			
			if(last == n) {
				last = n.prev;
			}
		}
	}
}

public class LRUCache {

	/**
	 */
	public static void main(String[] args) {

		
		LRU<String, String> cache = new LRU<String, String>(3);
		
		cache.put ("1", "one");                           // 1
		cache.put ("2", "two");                           // 2 1
		cache.put ("3", "three");                         // 3 2 1
		cache.put ("4", "four");
		System.out.println(cache.get("1"));
		cache.put ("3", "three");
		cache.put ("4", "foure");
		System.out.println(cache.get("4"));
		System.out.println(cache.get("2"));
		System.out.println(cache.get("3"));
		
		cache.put ("5", "five");
		System.out.println();
		System.out.println(cache.get("2"));
		System.out.println(cache.get("3"));
		System.out.println(cache.get("4"));
		System.out.println(cache.get("5"));
		
		
	}

}
